InnoDB中一颗B+ Tree能存储多少条数据
磁盘的结构
在回答这个问题之前，我们先来复习一下计算机机械磁盘的结构，如下图：
磁头（head）：主要就是读取磁盘表面磁方向和改变其方向，每个盘面有一个磁头，它极其贴近地悬浮在盘面上，但是绝对不与盘面接触，否则会损坏磁头和盘面；
磁道（track）：磁道是单个盘面上的同心圆，当磁盘旋转时，磁头若保持在一个位置上，则每个磁头都会在磁盘表面划出一个圆形轨迹，这些圆形轨迹就叫做磁道，一个盘面上的磁道可以有成千上万个。相邻磁道之间并不是紧挨着的，这是因为磁化单元相隔太近时磁性会产生相互影响，同时也为磁头的读写带来困难。
柱面（cylinder）：在有多个盘片构成的盘组中，由不同盘片的面，但处于同一半径圆的多个磁道组成的一个圆柱面。
扇区（sector）：磁盘上的每个磁道被等分为若干个弧段，这些弧段便是硬盘的扇区$Sector$。硬盘的第一个扇区，叫做引导扇区。扇区是被间隙$gap$分割的圆的片段，间隙未被磁化成0或者1。注意，扇区是读写磁盘最基本的单位，如果一个扇区因为某种原因被破坏，那么整个扇区的数据都会受影响。一个机械硬盘扇区的容量一般为512字节
单盘面结构图：
磁盘容量
Megatron747磁盘是一个典型的vintage-2008的大容量驱动器，它具有以下特性：8个圆盘，16个盘面，每个盘面有65536个磁道，每个磁道（平均）有256个扇区，每个扇区可以存储4096个字节（byte）
那整个磁盘容量的算法是：
16个盘面，乘以65536个磁道，乘以256个扇区，再乘以4096字节，即1665536256*4096=2^40 byte，也就是1TB的容量。
InnoDB存储引擎
在计算机中，磁盘存储数据最小单元是扇区，一个扇区的大小是512字节，而文件系统（例如XFS/EXT4）的最小单元是块，一个块的大小是4k，而对于InnoDB存储引擎也有自己的最小储存单元，页（Page），一个页的大小是16K。
InnoDB的所有数据文件（后缀为ibd的文件），大小始终都是16384（16k）的整数倍。
磁盘扇区、文件系统、InnoDB存储引擎都有各自的最小存储单元。
考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO，这个理论对于索引的数据结构设计非常有帮助。
事实1： 不同容量的存储器，访问速度差异悬殊。
- 磁盘(ms级别) << 内存(ns级别)， 100000倍
- 若内存访问需要1s，则一次外存访问需要一天
- 为了避免1次外存访问，宁愿访问内存100次…所以将
最常用的数据存储在最快的存储器中
事实2 ： 从磁盘中读 1 B，与读写 1KB 的时间成本几乎一样
从以上数据中可以总结出一个道理，索引查询的数据主要受限于硬盘的I/O速度，查询I/O次数越少，速度越快。
$B+\ Tree$
在InnoDB存储引擎中，每一个page对应B+ Tree的一个节点(Node)
根节点：InnoDB树的根节点由索引字段值和指针组成
叶节点：InnoDB的叶节点由索引字段值和对应的完整记录(row)组成
一般来说，B+ Tree的高度为3
现在，我们回到最开始的问题：一颗InnoDB的B+树大概存储多少条数据？
假设索引为主键索引，主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，这样一共14字节。
这样根节点大约可以存放的指针个数约为：$16384/14=1170$。即意味着内部节点一共有大约1170个。
对于每一个内部节点来说(上图第二层)，大约含有$16384/14=1170$个指针，意味着每一个内部节点对应大约1170个叶子节点。则一共有大约$1170*1170$个叶子节点
叶子节点，假设一条数据的大小为$1K$， 则每个叶子节点大约存放$16k / 1k =16$条数据。
至此，我们可以算出颗InnoDB的B+树大约能存数据为：
1 | 1170*1170*16=21902400 |
答案为：两千多万条！
也就是说，对于一个B+ Tree，从两千万条的数据中查找一条数据，只需要进行3次$I/O$.效率极大的得到了提升！！
